// 2025/9/14
// 整数转罗马数字

class Solution {
public:
    string intToRoman(int num) {
        string ans;
        int i = 0;
        while(num)
        {
            for(; i < roman.size(); i++)
            {
                if(num >= roman[i].first)
                {
                    num -= roman[i].first;
                    ans += roman[i].second;
                    break;
                }
            }
        }
        return ans;
    }
    static vector<pair<int, string>> roman;
};
vector<pair<int, string>> Solution::roman = {
    {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, 
    {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"}, 
    {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
};